package buaa.leetcode.String;

import java.util.ArrayList;
import java.util.List;

public class GenerateParentheses {
	public static List<String> generateParenthesis(int n){
		if( n == 0){return null;}
		List<String> result = new ArrayList<String>();
		List<String> newResult = new ArrayList<String>();
		result.add("()");
		if(n == 1){
			return result;
		}
		for( int i = 2;i <= n; i++){
			for(String tmp : result){
				newResult.add("()"+tmp);
				newResult.add("("+tmp+")");
				if(!newResult.contains(tmp+"()")){
					newResult.add(tmp+"()");
				}
			}
			result = new ArrayList<String>(newResult);
			newResult.clear();
		}
		return result;
	}
	public static void main(String[] args) {
		List<String> haha = generateParenthesis(3);
		for(String tmp : haha ){
			System.out.println(tmp);
		}

	}

}
